package com.mdnote.practice.generic_recursion;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/9/15
 * @description 序列化二叉树
 */
public class LeetCode297 {

    public static void main(String[] args) {
        // 我们直接使用前序遍历把
        LeetCode297 leetCode297 = new LeetCode297();
        TreeNode root = new TreeNode(10);
        root.left = new TreeNode(5);
        root.right = new TreeNode(15);
        root.left.left = new TreeNode(2);
        String serialize = leetCode297.serialize(root);
        System.out.println(serialize);

        leetCode297.deserialize(serialize);
        System.out.println(serialize);


    }

    private void preOrder(TreeNode node, StringBuilder stringBuilder) {
        if (node == null) {
            stringBuilder.append("null,");
        } else {
            stringBuilder.append(node.val).append(",");
            preOrder(node.left, stringBuilder);
            preOrder(node.right, stringBuilder);
        } 
    }

    private TreeNode preOrder(TreeNode node, List<String> list) {

        String temp = list.remove(0);
        if ("null".equals(temp)) {
            return null;
        }

        node = new TreeNode(Integer.parseInt(temp));
        node.left = preOrder(node.left, list);
        node.right = preOrder(node.right, list);
        return node;
    }

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder stringBuilder = new StringBuilder();
        preOrder(root, stringBuilder);
        return stringBuilder.toString().substring(0, stringBuilder.length() - 1);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] strings = data.split(",");
        List<String> list = new ArrayList<>();
        Collections.addAll(list, strings);

        return preOrder(null, list);
    }

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
}
